GML - Mini-Challenge 3 - FS 2022

Ausgabe: Montag, 23. Mai 2022
Abgabe: Sonntag, 12. Juni 2022, bis 24 Uhr

In diesem Mini-Challenge untersuchen wir die Struktur eines Datensatzes von Sonnenspektren.

Cédric Huwyler hat uns freundlicherweise die Daten dafür bereitgestellt. Es handelt sich dabei um Daten gesammelt von der Nasa Iris Mission: https://iris.lmsal.com/

Du findest etwas mehr Kontext auf folgender DS-Spaces Seite: https://ds-spaces.technik.fhnw.ch/iris-centroid-browser/

Vorgaben zu Umsetzung und Abgabe

Für die Erarbeitung der Inhalte darf zusammengearbeitet werden. Die Zusammenarbeit ist dabei aber auf algorithmische Fragen und Verständnisaspekte beschränkt.

Es darf kein Code oder Text von anderen oder vom Internet kopiert werden.


Aufgabe 1 (4 Punkte)

Lade den Datensatz der Sonnenspektren von folgendem Link herunter ( https://drive.switch.ch/index.php/s/SfcNAisJNpTxCrh ) und füge ihn dem data-Verzeichnis in diesem Repo zu (der Datensatz soll nicht committed und gepushed werden). Lade dann (data/iris_sun_spectra.npy) mit der Funktion np.load. Verwende einen relativen Pfad.

Der Wellenlängenbereich der Spektren ist 279.414 nm - 280.572 nm. Die Intensität der Spektren ist auf 1 normiert.

Visualisiere einige (~ 100) zufällige Beispiele nebeneinander in einer Figure in Subplots und beschreibe was du vorfindest.

Daten einlesen

Visualisieren 100 Beispiele

In allen Samples fallen die zwei Picks, bei denen die Intensität auf nahezu 1 springt, als Muster auf. Zudem gibt es zwischen diesen Picks in vielen Fällen ein Anstieg und Abfall der Intensität wobei die maximale Stärke der Intensität unterschiedlich sein kann. Dieses Muster kann auch unterhalb und oberhalb der gemessenen Wellenlänge beobachtet werden

Aufgabe 2 (8 Punkte)

Schreibe eine Klasse, analog einer Transformer-Klasse in scikit-learn, welche die Principal Components mittels Singular Value Decomposition berechnet.
Für einen beliebigen Datensatz sollen dabei alle möglichen Principal Components berechnet werden.

Nach Ausführen der fit-Methode, soll ein Objekt die Attribute components_ und variance_ aufweisen, welche die Principal Components als Zeilenvektoren, bzw. die Varianz des Datensatzes entlang der Komponenten ausweist.

Konstruiere und visualisiere ein einfaches 2-dimensionales Beispiel mit welchem du zeigst, dass deine Klasse wie erwartet funktioniert. Zeige insbesondere, dass die erste Principal Component tatsächlich in Richtung der grössten Varianz zeigt und dass die Berechnung der Varianzen entlang der Principal Components berechnet stimmen. Erkläre diese Verifikation der Funktionstüchtigkeit.

Einfaches 2-d Beispiel test

Zeigen das PCA funktioniert
Die Klasse PCA() berechnet mit der Singulärwertzerlegung die Eigenwerte und Eigenvektoren der Kovarianzmatrix von X_samplenorm. Die Daten sollen in Standardisierter oder Gemittelten Form vorliegen (PCA Klasse hat eine Funktionen dafür). `componentsgibt die Eigenvektoren zurück undvariance_` die prozuentale Erklärung der Daten durch die einzelnen Principal Components

Zeigen, dass die grösste PC entlang der grössten Varianz zeigt
components oder loading scores beschreiben die Eigenvektoren der Kovarianzmatrix (SVD() -> Matrix V).
In den Beispieldaten enthalten sind zwei Attribute x1 und x2 beide erhalten einen Eigenvektor, der entlang der grössten Varianz der Daten zeigt. Für die PCA werden die Achsen anhand der Eigenvektoren gedreht.

Wie in den obigen Grafiken erkennbar ist, sind die Eigenvektoren aus den Inputdaten und die Eigenvektoren der Kovarianzmatrix aus den Inputdaten identisch.

Zeigen der prozuentalen Erklärung der Varianz je Prinzipal Component für einmal svd(Inputdaten) und svd(covarianz).
In beiden Fällen erklärt pc1 rund 98% der Variation der Daten und pc2 die restliche Variation von 0.1%.

Zeigen das PCA in Richtung der grössten Varianz entlang PCA berechnet wird
Durch die Funktion U, S, V = np.linalg.svd(X) werden die Eigenwerte in S und die Eigenvektoren in V bereits nach den grössten Eigenwerten (oder wichtigste Prinzipal Componenten) sortiert. Wird das Produkt aus den Eigenvektoren mit den X Daten verrechnet wird eine Drehung der Daten entlang der wichtigsten PC erstellt. In unserem Fall entspricht dies x1 aus den Beispieldaten die auf der X-achse mit pc1 abgebildet sind und die höchste Variation der Daten zeigt. Die zweite wichtige PC landet auf der Y-achse in pc2. Bei höheren Dimensionen gilt das gleiche Muster.

Neben der .fit() Methode ist in der Klasse PCA() auch eine .fit_transform() Methode für eine direkte Matrix Reduktion verfügbar. Mit .fit_transform_covar() wird die Kovarianzmatrix verwendet um die Eigenvektoren zu berechnen. Es können die Anzahl verwendeter Komponenten übergeben werden oder eine Mindestanforderung an die prozentuale Erklärung der Daten gefordert werden. Übliche Werte liegen diese zwischen 0.9 - 0.99.

Ausgeben der Reduzierten Daten

Original Daten

Reduzierte Daten mit svd auf Inputdaten und durch die Eigenvektoren der Covarianzmatrix der Inputdaten. Zeigen das beide gleich)

In der Matrix X_reduced ist ersichtlich dass die Werte der wichtigsten PC (pc1) erhalten bleibt, pc1 kann 89% der Daten Variation erklären.

Testen ob PCA von sklearn zum selben Ergebniss kommt

Test PCA eigene Klasse im Vergleich zu PCA Sklearn
Die Resultate sind identisch, somit gezeigt und geprüft dass die Berechnungen korrekt sind.

Aufgabe 3 (6 Punkte)

Zeige (analytisch), dass die Principal Components die Eigenvektoren der Kovarianzmatrix eines Datensatzes sind. Was sind die Eigenwerte?

Lies das Kapitel von Jolliffe (Jolliffe, Principal Component Analysis, Springer, 2002) im Verzeichnis Literatur in diesem Repo für Inspiration.

Erkläre was dies bedeutet.

Zeigen das Principal Components die Eigenvektoren der Kovarianzmatrix des Datensatzes sind

Bemerkung
Laut Jolliffe [Principal Component Analysis, Springer, 2002, Seite 6] werden die Principal Components von PCA manchmal als Eigenvektoren ($\alpha_k$) der Kovarianzmatrix genannt. Er schreibt aber, dass die Principal Components besser als die abgeleiteten Variablen $\alpha_k^Tx$ und die Eigenvektoren $\alpha_k'$ als 'loadings' der PC's zu beschreiben wären. Bei der Recherche in der Literatur und im Web werden beide Varianten verwendet, daher sollte man darauf achten und kurz prüfen auf welche Form oder Definition sich die Autoren beziehen. In dieser Challenge werden die Principal Components als die Eigenvektoren gesehen.

Die Kovarianzmatrix $C$ von X kann mit folgender Formel berechnet werden:
$\bar{x}$ ist dabei der mean vector von $x_i$

$$ \Sigma = C = Cov(X) = \frac{1}{n-1} \left( (X - \bar{x}) (X - \bar{x}) \right) $$

oder mit $B$ als zentrierte Matrix gilt folgendes für die Kovarianzmatrix $C$:

$$ B = X - \bar{X}$$$$ \Sigma = C = Cov(B) = B^T B$$

Die Eigenvektoren $V$ von $B$ können mit der Singulärwertzerlegung berechnet werden: $$ B = U\Sigma V^T$$

Für die Berechnung der Eigenvektoren der Kovarianzmatrix $B^TB$ gilt sie selbe Formel:

$$ C = B^TB = (U\Sigma V^T)^T (U\Sigma V^T) = V\Sigma^T U^T U \Sigma V^T = V(\Sigma^T \Sigma) V^T$$

Die Eigenwerte befinden sich in $D = (\Sigma^T \Sigma)$ und damit folgt:

$$C = B^TB = VDV^T$$$$ CV = VD $$

Damit kann gezeigt werden dass die Eigenvektoren $V$ der Kovarianzmatrix gleich der Eigenvektoren $V$ aus der Matrix B sind.

Theorie und Vorteile von Symmetrischen Matrizen
Die Kovarianzmatrix ist eine symmetrische Matrix und diese haben besondere Eigenschaften:

Mit der Singelwertzerlegung können die Eigenvektoren berechnet werden, $ C = U\Sigma V^T$. Die Eigenvektoren (oder Principal Componente) mit den höchsten Singulär werten, zeigen in die Richtung der grössten Variation der Daten. Die Anzahl der benötigten PC ist von Interesse, um beispielsweise 90% der Information von Daten beizubehalten.

Die Dimensionsreduktion berechnet sich anschliessend aus $P_{rincipal} C_{omponentes} A_{Analysis} = X V[:,k:]$, dabei steht $k$ für die Anzahl PC (Eigenvektoren) die man verwenden möchte. Die PC sind als Spalten in $V$ enthalten. Je mehr PC's verwendet werden umso mehr Varaition der Daten wird beibehalten. Ein Beispiel für $k=2$:

$$ PCA = X V[:,k:] = \left( \begin{matrix} x_{00} & x_{01} \\ x_{10} & x_{11} \\ x_{n0} & x_{n1} \end{matrix} \right) \left( \begin{matrix} v_{00} & v_{01} & v_{01} \\ v_{10} & v_{11} & v_{11} \end{matrix} \right) $$

Dabei werden die k PC's (Eigenvektoren) von $V$, die in Richtung der höchsten Varianze der Daten zeigen, mit den original Daten $X$ verrechnet. Es folgt eine Projektion der Daten in Richtung der Eigenvektoren mit der höchsten Varianz. Somit erreicht PCA eine Dimensionsreduktion in dem sie die original Daten entlang der k wichtigsten Eigenvektoren projiziert.

Was sind Eigenwerte?
In vielen Anwendungen beschreiben Eigenwerte ($\lambda$) Eigenschaften von mathematischen Modellen.

Aufgabe 4 (11 Punkte)

Berechne die Principal Components des Datensatzes der Sonnenspektren.

Zeichne die kumulative Summe der Varianzen entlang der aufsteigenden Principal Components.

Wieviele Components brauchen wir, um 95 % der Varianz des Datensatzes zu erhalten?
Rekonstruiere die Spektren aus diesen $K$ Components und zeichne Original und Rekonstruktion für 100 Beispiele in den gleichen Plot.

Zeichne die $K$ Principal Components.

Projiziere die Spektren auf die ersten beiden Principal Components und visualisiere die Spektren im neuen Koordinatensystem.

Diskutiere sämtliche Plots.

Verwenden der Daten mit PCA führte zu Systemproblemen
Die Eigenvektoren mit svd(df_iris) direkt aus dem Datensatz zu lesen überforderte den Rechner für bereits 50'000 Datenpunkte. Daher ist es zwingend notwendig die Eigenvektoren aus der Kovarianzmatrix zu berechnen. $C = B^TB$.

Zeichne kumulative Summe der Varianz
Es braucht 6 Principal Components aus den totalen 240 Stück um 95% der Variation in den Daten zu erklären.

Zeichne Original und Rekonstruktion für 100 Beispiele im gleichen Plot
Die Funktion .rekonstruktion() aus der PCA() Klasse versucht die originalen Daten zu rekonstruieren. Mit Hilfe der Elemente von SVD, aber unter der Verwendung der Anzahl n_componentns die bei der PCA als Haupträger der Variation der Daten gefunden wurden. Aus dem obigen "variance_explained" Plot sehen wird das mit bereits 6 PC's reichen um > 95% der Daten Varaition zu erklären.

Die obigen 100 Spektren zeigen die originalen Sonnenspektren (blau) und die rekonstruierten Sonnespektren (grün) nach PCA und 6 verwendeten Principal Components.

Projiziere die Spektren auf die ersten beiden Principal Components

Hier ist ersichtlich dass die höchste Varianz der Daten auf der PC1, entlang der X-Achse, liegt. Die zweit wichtigste Varianz (PC 2) liegt auf der Y-Achse.

Aufgabe 5 (10 Punkte)

Nun wenden wir uns Non-negative Matrix Factorization (NMF) zu.

Verwende NMF von scikit-learn, um eine Zerlegung der Datenmatrix zu berechnen.

Entwickle also ein sinnvolles NMF-Modell für den Sonnenspektren Datensatz. Wie kannst du hier die Anzahl Komponenten wählen?

Ein Datenpunkt soll in deinem Ansatz nur durch einen kleinen Teil der Komponenten repräsentiert werden können. Inwiefern hat dies einen Einfluss auf die Wahl der Regularisierung?

Welche übergeordneten ML-Entwicklungs- und Model-Selection-Prinzipien kannst du hier einbringen, begründe.

Rekonstruiere die Spektren aus den gefundenen Komponenten und zeichne Original und Rekonstruktion für 100 Beispiele in den gleichen Plot.

Zeichne die gefundenen Komponenten.

Wie kannst du visualisieren und aufzeigen, dass die Sonnenspektren tatsächlich nur aus wenigen Komponenten rekonstruiert werden?

Diskutiere sämtliche Ergebnisse und vergleiche die Resultate mit Aufgabe 3.

NMF von sklearn und entwickle ein NMF-Modell für den Sonnenspektren Datensatz
Doku NMF. Folgend wird mit NMF().get_params().keys() welche Parameter für das Modell zur Verfügung stehen. Mit 'n_components' kann die Anzahl Components bestimmt werden.

Die Matrizenzerlegung auf dem ganzen Datensatz dauert lang, zum ausprobieren und testen von NMF wird ein sample des orginalen Datensatze verwendet:

Einfluss der Regularisierung
Mit alpha kann ein Regularisierungs Parameter gesetzt werden, wenn $\alpha = 0$ dann findet keine Regularisierung. In der nächsten Version (1.2) wird dieser Parameter jedoch entfernt und es stehen neu 'alpha_W' und 'alpha_H' zur Verfügung. Somit können die Matrizen W und H seperat regularisiert werden.

Mit alpha_W und alpha_H werden die Gewichte des Algorithmus gesetzt, somit kann der Einfluss der Koeffizienten oder der Komponenten eingeschränkt, oder eben regularisiert werden. Mit der Option 'same' werden Parameter gleich regularisiert, es können aber auch unterschiedliche Regularisierungen angewendet werden zum Beispiel L1 auf W und die L2-Norm auf H.

Die L1-Norm führt dazu das gewisse Elemente auch exakt 0 werden können und somit, zum Beispiel falls eines Koeffizienten in der W Matrix 0 werden, haben die entsprechenden Komponenten keinen Einfluss. Da der Algorithmus iterative jeweils W und H optimiert muss wohl getestet werden, welche Optionen der Möglichkeiten die besten Resultate liefern, evtl. kann mit einer Metrik auf den Rekonstruiertem Datensatz einen Unterschied gemessen werden.

Folgend soll der single Parameter $\alpha$ für die Regularisierung getestet werden.

Die Funktion reconstruction_err_ berechnet den Fehler bei der Rekonstruierung der Daten. Also eine Kostenfunktion auf der die Regularisierung getestet werden kann.

Bemerkung: Der Parameter max_iter wurde bis auf 2500 hochgesetzt, um Warnung zu verhindern. Die Berechnungszeit dauert allerdings einiges länger aber die Grafik die die Regularisierungen zeigen bleiben praktisch identisch. Daher wurde max_iter=200 belassen und die Warnungen ausgeschaltet

Die obige Grafik zeigt den Einfluss der Regularisierung. Bei 'rot' findet keine Regularisierung statt und die Kosten werden mit zunehmenden Komponenten immer kleiner. Bei den Linien 'blau' und 'grün' beeinflusst die Regularisierung NMF ab der vierten Komponente und ab der Zehnten Komponente bleiben die Kosten konstant und es findet keine Verbesserung mehr statt. Overfitting verhindert.

Welche übergeordneten ML-Entwicklungs- und Model-Selection-Prinzipien kannst du hier einbringen

Rekonstruiere die Spektren aus den gefundenen Komponenten und zeichne Original und Rekonstruktion für 100 Beispiele in den gleichen Plot.
Die Rekonstruktion aus dem NMFf-Modell erhält man durch das Produkt von W @ H ~ df_iris.

Die obigen 100 Spektren zeigen die originalen Sonnenspektren (blau) und die rekonstruierten Sonnespektren (grün) nach NMF und 6 verwendeten Components.

Zeichne die gefundenen Komponenten
zeichnen von Component 1 auf der X-Achse und Component 2 auf der Y-Achse. Auch bei der NMF Reduktion kann gesehen werden, dass die Variation der ersten Komponente höher ist als die der zweiten Komponente.

Wie kannst du visualisieren und aufzeigen, dass die Sonnenspektren tatsächlich nur aus wenigen Komponenten rekonstruiert werden?

Die Kostenfunktion von NMF berechnet die L2-Distanz der Datenpunkte zwischen Original und Reduktion. In der Kostenfunktionsgrafik ist ersichtlich, dass die Kosten mit mehr Komponenten gegen 0 laufen werden (bis alle Komponenten des originalen Datensatzes verwendet wurden). Man kann aber auch herauslesen, dass bei $k<6$ die Kosten am stärksten sinken. Die Distanz oder der Fehler wird ab $k>6$ zwar weiter verkleinert, jedoch nicht mehr gleich stark. Somit kann gezeigt werden dass nur einen Teil der Komponenten verwendet werden kann und denoch der grösste Teil der Daten erhalten werden kann.

Aufgabe 6 - K-Means (8 Punkte)

K-Means ist ein Clustering-Algorithmus. Mit K-Means können wir einen Datensatz in $K$ Gruppen (Cluster) unterteilen. Eine Funktion $C(i) \in \{ 1, \dots, K \}$ ordnet dabei jedem Datenpunkt $i$ einen Cluster $k$ zu.

Die $K$ Gruppen werden dabei über $K$ Zentroiden, Clustermittelpunkte $\mu_k$, charakterisiert. Datenpunkte (Pixelwerte in unserem Fall) werden dem Zentroiden zugeordnet, der ihnen am nächsten ist. Der K-Means-Algorithmus (siehe unten) findet dabei ein lokales Minimum für die Funktion

$$ J(C) = \sum_{k=1}^{K} \sum_{C(i)=k} ||x^{(i)} - \mu_k||^2 $$

Er minimiert also den summierten quadrierten Abstand der Datenpunkte zu ihrem Zentroiden.

Da der Algorithmus nur ein lokales Minimum findet, initialisiert man den Algorithmus in der Regel mehrfach und behält am Schluss die Lösung mit dem kleinsten Wert für die Kostenfunktion.

Ein Durchlauf / eine Initialisierung des Algorithmus funktioniert wie folgt:


K-Means Algorithmus

Initialisierung: Wähle $K$ Zentroiden zufällig aus den gegebenen Datenpunkten.

Schritt 1: Für gegebene Zentroiden $(\mu_1, .., \mu_k)$ ordne man sämtliche Datenpunkte jeweils jenem Cluster zu, dessen Zentroid dem jeweiligen Datenpunkt am nächsten ist. Also

\begin{eqnarray} C(i) = \mathsf{argmin}_k ||x^{(i)} - \mu_k||^2 \end{eqnarray}

Schritt 2: Für eine gegebene Cluster-Zuordnung $C$ minimiere man die 'Gesamt-Cluster-Varianz' durch Aktualisieren der Zentroiden mit:

\begin{eqnarray} \mu_k = \frac{1}{N_k} \sum_{C(i)=k}x^{(i)} \end{eqnarray}

$N_k$ sind die Anzahl Datenpunkte, die k zugeordnet sind.

Schritt 3: Man wiederhole die Schritte 1 und 2 bis sich die Zentroiden nicht mehr verändern oder der Wert der Funktion $J(C)$ sich kaum mehr verbessert.


Vervollständige die folgende Klasse, welche den K-Means-Algorithmus umsetzen soll.

Zeige anhand eines konstruierten Beispiels, dass dein Algorithmus zuverlässig funktioniert.
Verwende zur Konstruktion des Beispiels sklearn.datasets.make_blobs.

Beispiel Daten erzeugen mit sklearn.datasets.make_blobs

Testen der KMeans() Klasse
Die Initialisierung der zufälligen Datenpunkte spielen eine wichtige Rolle, da es je nach Startwert zu anderen Ergebnissen kommen kann. Die Empfehlung ist, die KMeans Clustering öfters auszuführen, um einige Kombinationen zu testen. Mit der Kostenfunktion wird dann die beste Aufteilung der Daten bewertet und die Werte entsprechend den minimalen Kosten verwendet. Auch ist die Wahl von $k$ wichtig, in den Beispiel daten sind deutlich drei Cluster zu erkennen. Soll ein Modell mit vier Cluster erstellt werden, geht das ohne Probleme, nur wird dann ein Cluster in zwei Untercluster aufgeteilt.

Folgend sollen ein paar Beispiele die unterschiedlichen Situationen verdeutlichen (dabei werden random_seed Werte gesetzt, womit Kmeans nur mit einer Samplewahl zurechtkommen muss):

  1. Beispiel: zufällige Datenpunkte wurden jeweils aus einem Cluster gezogen (erreicht mit random_seed=13).
  2. Beispiel: zwei der zufällige Datenpunkte kommen aus demselben Cluster (erreicht mit random_seed=1).
  3. Beispiel: Die Daten zeigen drei Cluster, KMeans soll aber vier Cluster aufteilen (erreicht mit random_seed=13).
  4. Beispiel: KMeans mit mehreren durchläufen, bis die tiefste Kostenfunktion gefunden wurde (random_seed=None)

Bemerkung: wird ein random_seed gesetzt werden alle samples gleichgezogen, daher ist der Wert der Kostenfunktion auch immer gleich

  1. Beispiel:
    Random Sample finden sich in jedem Cluster und die Mittelwerte der Zentroiden können schnell konvergieren.
  1. Beispiel:
    Fallen zwei der random Datenpunkte in einem Cluster, fällt die Aufteilung bereits nicht mehr gleich aus. Der KMeans Algorithmus verschiebt die Mittelpunkte, bis die Kostenfunktion minimal ist. Dieses Beispiel zeigt warum KMeans öfter ausgeführt werden sollte. Mehrer Versuchen erhöhen die Chancen für eine 'beste' Cluster Aufteilung der Daten.
  1. Beispiel:
    Die Aufteilung in mehr Cluster geschieht ohne Probleme, je mehr Cluster verwendet werden umso genauer kann die Kostenfunktion werden. Wie genau $k$ gewählt werden muss folgt in einer späteren Erklärung. Hier soll gezeigt werden, dass die Wahl von $k$ entscheidend ist. Die Beispieldaten haben drei Cluster, durch die Wahl von $k=4$ wurde einer der Cluster weiter aufgeteilt.
  1. Beispiel:
    Hier wird KMeans öfter initialisiert und die gefundenen Werte zum minimalen Kostenfunktionwert verwendet. In diesem Beispiel sehen wir, auch wenn die Wahl der Initial Datenpunkte im selben Cluster starten, können die Zentroide so verschoben werden, dass die Kostenfunktion minimal wird und die Mittelpunkte der Cluster gefunden werden.
    Es gibt Situationen in denen Random Datenpunkte keine gute Initialisierung treffen, diese werden von KMeans verworfen (zum Beispiel, wenn ein Cluster nicht zugeordnet wird - Slicing nach Klassen dann nicht möglich).

Bemerkung: folgender Code kann mehrmals ausgeführt werden, man sieht die unterschiedlich gewählten random Datenpunkte. Diese führen aber jeweils zur selben Clusterbildung

Testen der Distanz Berechnung von cdist() mit der numpy Norm Funktion
$ dist_{xo} = ||x_0 - \mu||^2$, $x_o$ = Datenpunkt, $\mu$ = Cluster Punkte

cdist() gibt die Distanzen auf den Zeilen aus, mit np.argmin(axis=1) den Index mit kürzeste Distanz suchen und Cluster zuordnen.

Aufgabe 7 - K-Means auf Sonnenspektren (7 Punkte)

Beschreibe nun in Worten was es bedeutet, diese Spektren zu clustern.

Nimm ein Clustering mit deiner Implementierung von KMeans der Sonnenspektren vor.

Bestimme einen sinnvollen Wert für $K$. Erläutere dabei dein Vorgehen und diskutiere auch alternative Möglichkeiten dafür.

Zeichne die Zentroiden.

Beschreibe und diskutiere deine Resultate.
Lege dabei Unterschiede von Zentroiden und Principal Components, sowie NMF Komponenten aus der ersten ule Mini-Challenge dar.

Könnte man K-Means auch als Matrizen-Zerlegung betrachten? Wie?

Beschreibung Cluster der Sonnenspektren
KMeans findet Strukturen oder unterschiedliche Eigenschaften in den Messdaten und 'gruppiert' dann gleiche oder ähnliche Messdaten in Clustern.

Um die Laufzeiten Überschaubar zu halten werden auch hier die Sampledaten anstelle des kompletten Datensatzes verwendet.

Cluster auf den Sonnenspektren
Achtung dieser Prozessschritt dauert einen Moment

Bestimme einen sinnvollen Wert für $K$
Um einen sinnvollen Wert für K zu suchen, sollen mehrere K für ein KMean Modell ausprobiert werden, die Kosten zu den unterschiedlichen $K$ Werten soll geplottet werden.

Die Wahl von $K$, also die Anzahl Cluster, die gebildet werden sollen, wird noch oft von Hand festgelegt. Die Wahl ist jedoch nicht immer einfach, im unsupervised learning bestehen keine Lables, daher gibt es mehrere korrekte Möglichkeiten um die Daten in Cluster aufzuteilen. Folgend zwei Möglichkeiten, um $k$ zu bestimmen:

  1. Zeichnen der Kostenfunktion zu verschiedenen $k$-Werten. Da die Kosten immer kleiner werden für höhere $k$-Werte, kann mit der 'Elbow Methode' versucht werden, optimale $k$-Werte zu finden. Die grösste Reduktion der Kosten findet man dann bei einem gewissen $k=elbow$, danach fallen die Kosten nicht mehr gleich stark. Diese Methode wird in der Praxis jedoch nicht oft verwendet da ein klarer Elbow Effekt nicht oft ersichtlich ist. Im obigen Plot fallen die Kosten nach $k=8$ weniger stark, aber ein Elbow Effekt ist nicht eindeutig zu sehen.
  2. Eine weitere Möglichkeit ist zu hinterfragen für welchen Zweck ein Clustering durchgeführt wird. Diese Fragestellung kann helfen eine gute Wahl für $k$ zu treffen. In Fall der Sonnenspektren könnten zum Beispiel die unterschiedlichen Intensitäten zwischen den zwei Picks in Klassen unterteilt werden. Zum Beispiel: Klasse a) keine Intensität zwischen den Picks, Klasse b) erhöhte Intensität, Klasse c) hohe Intensität zwischen den zwei Picks Klasse d) unterschiedliche Formen von den zwei Hauptpicks, etc.

Nach Andrew Ng kann die Kostenfunktion gezeichnet und auf den 'Elbow' geprüft werden, falls dieser vorhanden ist kann $k=elbow$ gesetzt werden. Ansonsten wird üblicherweise die Frage nach dem Zweck der Cluster verwendet.

Quelle Andrew NG

Zeichnen der Zentroide
Die Zentroiden beschreiben den Mittelpunkt einer Klasse. Somit können die Zentroiden direkt als Durchschnittsmesswert je Klasse gesehen und auch geplottet werden.

Beschreiben der Resultate
In obigen Plot sind die Mittelwerte der unterschiedlichen Cluster abgebildet. KMmeans findet Strukturen und teilt diese in Klassen ein. Man kann sehen, dass die zwei Picks (~279,6 nm, ~280.35nm) immer vorhanden sind, jedoch variieren die Intensitäten zwischen den zwei Picks. Man sieht tiefe, mittlere und starke Intensitäten dazwischen. Auch gibt es Cluster bei denen die Spitzen der Picks in zwei Spitzen unterteilt sind.

Das Clustering von KMeans findet also unterschiedliche Eigenschaften von Messungen und teilt diese in unterschiedliche Klassen ein. Prüfbar sind die Resultate, indem die Zentroiden gezeichnet werden. PCA projiziert die Messdaten auf die entsprechenden Principal Components (Eigenvektoren mit den höchsten Eigenwerten) und reduziert somit die Daten. Das Ziel ist mit wenigen PC möglichst viel der Variation der Daten erklären zu können. Bei NMF findet auch eine Reduktion der Datenmatrix statt (in Koeffizienten und Komponenten). Die Cluster von KMean könnten den Komponenten von NMF sehr ähnlich sein. Beide zeigen eine Art Grundstruktur der Daten. Durch die Koeffizienten in NMF werden die Komponenten so verändert, dass die Messdaten abgebildet werden können. Für PCA könnte dasselbe für die wichtigsten Eigenvektoren gelten.

KMeans als Matrizen Zerlegung betrachten?
Auch wenn KMean die Datenmenge nicht direkt reduziert, führt das Clustering zu einer Aufteilung der Daten und legt somit die Grundstruktur der Daten durch die Zentroide frei. Somit kann auch bei KMeans von einer Matrizen Zerlegung gesprochen werden.

Aufgabe 8 (5 Punkte)

Visualisiere die Cluster im Raum der ersten beiden Principal Components zusammen mit ihren Zentroiden.

Beschreibe und diskutiere deine Resultate. Entsprechen sie deinen Erwartungen?

Der KMeans Algorithmus kann beliebig oft ausgeführt werden und landen jeweils bei der gleichen Cluster Aufteilung. Somit kann gezeigt werden das ein Clustering der Datenpunkten in den reduzierten Daten gefunden wird. Durch die PCA können die reduzierten Daten jedoch nicht mehr in Wellenlängen erklärt werden, was eine Interpretation aus meiner Sicht schwierig macht. Modell können jedoch von den reduzierten Daten profitieren und trotzdem Muster erkennen, wie hier ersichtlich.

Folgend sollen die Zentroide von KMeans auf dem reduzierten Datensatz untersucht werden
Um die Cluster von Kmeans besser zu verstehen können die Zentroide rekonstruiert und grafisch dargestellt werden.

Mit PCA wurde der ursprüngliche Datensatz reduziert und zwei Principal Components beibehalten, damit können ca. 80% der Datenvariation erklärt werden. Die Anwendung von KMeans ($k=8$) auf dem reduziertem Datensatz und die Rekonstruktion dieser, gibt uns die obige Grafik mit den Zentroide (Mittelwerte) der Cluster.
Die Anordnung der Cluster ist unterschiedlich zu der in Aufgabe 7, aber es kann verglichen werden, dass dieselben Cluster Einteilungen entstehen wie auf dem originalen Datenset in Aufgabe 7. Somit konnte mit PCA die Dimensionen der Daten von 240 Dimensionen auf gerade mal 2 Dimensionen herunter gebrochen werden und das Clustering von Kmeans kommt dennoch zum selben Resultat. Das zeigt das PCA ein mächtiges Instrument ist, um Daten zu reduzieren und ohne grosse Informationsverluste.

Aufgabe 9 (4 Punkte)

Beschreibe abschliessend die drei hier verwendeten Unsupervised Learning-Methoden miteinander. Was zeichnet sie aus, was unterscheidet sie?

Unsupervise Learning-Methoden verwendet:

  1. PCA
  2. NMF
  3. KMeans

PCA und NMF
PCA und NMF reduzieren beide die Dimensionen der Daten. Mit der Anzahl verwendeten Prinicpal Components von PCA wird probiert die Dimension der Daten zu verkleinern und gleichzeitig möglichst viel der Datenvariation zu erhalten. NMF findet die wichtigen nicht-negativen Features. Für grosse Datensätze bringt dies hinsichtlich Berechnungsleistung erhebliche Vorteile, um zum Beispiel Modelle zu trainieren. PCA erstellt mit den Eigenvektoren eine reduzierte Matrix, die eindeutig ist. Bei NMF hingegen werden die Matrizen W und H random initialisiert und gegenseitig optimiert, weshalb die reduzierte Matrix jeweils unterschiedlich Ergebnisse enthalten kann (die Initialisierung wird benötigt um mit Gradient Descent das Minimum von W und H zu suchen). Für die bessere Reproduzierbarkeit könnte die Initialisierung jedoch angepasst oder dokumentiert werden.

Bei NMF sind nur nicht negative Werte erlaubt, was zu nicht negative Matrizen führt, dies ist zum Beispiel bei Daten mit Bildern oder Texten der Fall. Auch beschreibt Element of statistical Learning (Seite 554), das im Vergleich zu PCA, sich NMF Strukturen oder Metadaten merken kann. Anhand von Bildern zeigt sich dies im Buchbeispiel, als lernen der Merkmale von Gesichtern (Nasen, Augen, Mund, etc). Die Komponenten bei Texten können als Topics gesehen werden (Topic-modeling).
Dieselben Daten mit PCA zu zerlegen kann zu nicht interpretierbare Werten in den reduzierten Matrix führen (negative Wort länge). Somit ist die Interpretierbarkeit von Matrizenzerlgung mit NMF besser als die Zerlegung mit PCA. PCA hat dafür keine Probleme mit negativen Werten in den Daten. Hinsichtlich des trainieren von Modellen liefern aber offenbar beide ähnliche Resultate.

NMF / PCA, KMeans
PCA und NMF sprechen beide das Thema 'curse of dimensionality' an. Falls zu viele Dimensionen vorhanden sind, kann KMeans schlechte Resultate liefern und die Dimension der Daten sollte vorab reduziert werden. Eine Reduktion der Dimensionen kann dann mit PCA oder NMF erfolgen und ggf. bessere Resultate für KMeans Cluster liefern.

Kmeans findet durch Cluster (oder Klassen), ebenfalls wie NMF, Strukturgrundlagen in den Daten und kann diese zuordnen. Die Zentroiden von KMeans können also auch als W Matrix von NMF gesehen werden.

Ende gml - mini Challenge 3
Student: Manuel Schwarz